#include <vector>
#include <iostream>
#include "Algorithms.h"
#include "Graph.h"
#include "Flow.h"
#include "Graph.h"
#include "OrientedGraph.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include "AbstractGraph.h"

using namespace std;


Algorithms::Algorithms()
{
}

/*---------------------glouton----------------*/
vector<int> Algorithms::glouton(const AbstractGraph  graph)
{
  vector<int> couverSommets;
  AbstractGraph copy(graph);
  while(!copy.hasNoEdge())
    {
      int indiceMax = 0;
      for (int i = 1; i<copy.getSize(); i++)
	{
	  if(copy.degre(i) > copy.degre(indiceMax))
	    {
	      indiceMax = i;
	    }
	}
      couverSommets.push_back(indiceMax);
      copy.delEdgeFromVertex(indiceMax);
    }
  return couverSommets;
}

/*-------------------opt-Tree----------------------*/
vector<int>  Algorithms::optTree(const Tree t)
{
  Tree copy(t);
  vector<int> cover;
  int_vect_vect v = copy.getAdjencyList();
 
  while(!copy.hasNoEdge()){
    for(int i=0; i<v.size();++i)
      {
	if(copy.degre(i) == 1)
	  {
	    cover.push_back(copy.getAdjencyList()[i][0]);
	    copy.delEdgeFromVertex(copy.getAdjencyList()[i][0]);
	  }
      }
  }
  return cover;
}

/*------------------------2Approche graphe-----------------*/
static void isIn(const AbstractGraph *g, AbstractGraph *t, int vertex, int * isMarked)
{
  isMarked[vertex] = 1;
  if(g->neighbours(vertex).size() !=0)
    {
      for (int i=0; i< g->neighbours(vertex).size(); ++i)
	{
	  if(isMarked[g->neighbours(vertex)[i]] == 0)
	    {
	      t->addEdge(vertex, g->neighbours(vertex)[i]);
	  
	      isIn(g, t, g->neighbours(vertex)[i], isMarked);
	    }
	}
    }
  else
    {
      if( vertex + 1 < g->getSize())
	isIn(g, t, vertex + 1, isMarked);
    }
}

void  Algorithms::parcoursProfondeur(const AbstractGraph *g, Tree *t, int vertexRoot)
{
  int *isMarked = (int*)malloc(sizeof(int) * g->getSize() );
  for(int i = 0; i<g->getSize(); i++)
    {
      isMarked[i]=0;
      t->addVertex();
    }
  isIn(g, t, vertexRoot, isMarked);

}

vector<int>  Algorithms::twoApprocheGraphe(AbstractGraph *g, Tree *t, int vertexRoot)
{
  parcoursProfondeur(g,t, vertexRoot);
  vector<int> cover;
  cover.push_back(vertexRoot);
  int_vect_vect v = t->getAdjencyList();
  for(int i=0; i<v.size();++i)
    {
      if(t->degre(i) >= 2)
	cover.push_back(i);
    }
  return cover;
}

/*------------------------2Approche Voisinage-----------------*/
vector<int> Algorithms::twoApprocheVoisinage(const AbstractGraph graph)
{
  vector<int> cover;
  AbstractGraph copy(graph);
  int vertex = 0;
  int vertexAdj = 0;
  while(!copy.hasNoEdge())
    {
      if(copy.degre(vertex)!=0)
	{
	  vertexAdj = copy.neighbours(vertex)[0];
	  cover.push_back(vertex);
	  cover.push_back(vertexAdj);
	  copy.delEdgeFromVertex(vertex);
	  copy.delEdgeFromVertex(vertexAdj);
	}
      else
	vertex++;
    }
  return cover;
}

/*---------------------------------------------------------------------------*/

vector<int> *
Algorithms::routesAndCircuits(AbstractGraph & g, int k)
{
  vector<int> cover;
  AbstractGraph copy(g);
  bool found = false;
  
  
  while(!copy.hasNoEdge())
    {
      // looking for a 1-degree vertex
      // or a 2-degree if not found
  
      int i = 0;
      int j = -1;
      while(i < g.getSize())
	{
	  if(copy.degre(i) == 2) //save the 2-degree vertex, just in case
	    j = i;
      
	  if(copy.degre(i) == 1)
	    break;
	  ++i;
	}
      
      if(i == copy.getSize()) //only circuits
	{
	  g.delEdge(i, g.neighbours(i)[0]); //if circuit, then turn it into a route
	  i = j;
	}

      int v = i;
      bool take = false;
      int u;
      copy.printGraph();
      do
	{    
	  u = v;
	  v = copy.neighbours(u)[0];
      
	  if(take || copy.degre(v) == 1) //take one under two, or at least one if single edge
	    cover.push_back(v);

      
	  take = !take;
	  copy.delEdge(u, v);
	}
      while(copy.degre(v) > 1);
    }

  if(cover.size() < k)
    return new vector<int>(cover);
  else
    return NULL;
}

/*-- --------------------------optimal for graph with a small cover ---------------------*/
vector<int> *
Algorithms::parametricAlgorithm(AbstractGraph & g, int k)
{
  int i = 0;
  static int l = 0;
  l++;
  vector<int> neighboors;
  bool end = false;
	
  if(k <= 0)
    return NULL;

  while (!end)
    { 
      end = (i == g.getSize() || g.degre(i) >= 3);
      ++i;
    }
  --i;
	
  //base case
  if(i == g.getSize())
    return routesAndCircuits(g, k);	
  //recursion
  int vertex = i;
  AbstractGraph graph1 = AbstractGraph(g);
  graph1.delEdgeFromVertex(vertex);
  vector<int>  * v1 = (k - 1 > 0) ? parametricAlgorithm(graph1, k - 1) : NULL;

  if(v1 != NULL)
    v1->push_back(vertex);

  AbstractGraph graph2 = AbstractGraph(g);
  vector<int> neighbours = g.neighbours(vertex);

  for(int j = 0;  j< neighbours.size(); ++j)
    graph2.delEdgeFromVertex(neighbours[j]);


  vector<int> * v2 = (k - neighbours.size() > 0) ?
    parametricAlgorithm(graph2, k - neighbours.size()) : NULL;

  if(v2 != NULL)
    v2->insert(v2->end(), neighbours.begin(), neighbours.end());
	
  if(v1 == NULL)
    return v2;
  if(v2 == NULL)
    return v1;

  if(v1 == NULL && v2 == NULL)
    return NULL;

  if(v1->size() < v2->size())
    return v1;
  else
    return v2;
}

//classic set intersection algorithm in O(n * log(n))
vector<int>
intersect(vector<int> vect1, vector<int> vect2)
{
  sort(vect1.begin(), vect1.end());
  sort(vect2.begin(), vect2.end());

  vector<int> intersection;

  int i = 0;
  int j = 0;

  while( i < vect1.size() && j < vect2.size())
    {
      if (vect1[i] == vect2[j])
	{
	  intersection.push_back(vect1[i]);
	  ++i;
	  ++j;
	}
      else
	if (vect1[i] > vect2[j])
	  ++j;
	else
	  ++i;
    }
  return intersection;
}



bool
fordFulkerson(Flow & f, vector<int> color, vector<vector<int> > neighbs, vector<vector<int> > prevs, int s, int t)
{
  queue<int> F;
  Flow g;
  F.push(s);
  map<int, int> father;
  while(color[t] == 0 && !F.empty())
    {
      int v = F.front();
      F.pop();
      for(int i = 0; i < neighbs[v].size(); ++i)
	{
	  int w = neighbs[v][i];
	  if(color[w] == 0 && !f.value(v, w))
	    {
	      color[w] = 1;
	      g.push(v, w, true);
	      father[w] = v;
	      F.push(w);
	    }

	}

      for(int i = 0; i < prevs[v].size(); ++i)
	{
	  int u = prevs[v][i];
	  if(color[u] == 0 && f.value(u, v))
	    {
	      color[u] = 1;
	      g.push(u, v, false);
	      father[u] = v;
	      F.push(u);
	    }

	}
      if(color[t] == 1)
	{
	  v = t;
	  int  u = father[v];
	  f.push(u, v, g.value(u, v));
	  while(u != s)
	    {
	      v = u;
	      u = father[v];
	      f.push(u, v, g.value(u, v)); 
	    }
	}
      color[v] = 2;
    }
  return (F.empty());
}
/*-----------------------------------------optimalBipartite------------------------*/

vector<int> Algorithms::optimalBipartite(BipartiteGraph &bg)
{
  vector<int> X = bg.getPartition1();
  vector<int> Y = bg.getPartition2();

  vector<int> S, T;

  //Constructing new graph
  OrientedGraph g =  OrientedGraph(bg);
  Flow f;
  for(int u = 0; u < Y.size(); ++u)
    g.delEdgeFromVertex(Y[u]);

  int s, t;

  s = g.addVertex();
  t = g.addVertex();

  for(int x = 0; x < X.size(); ++x)
    g.addEdge(s, X[x]);

  for(int y = 0; y < Y.size(); ++y)
    g.addEdge(Y[y], t);

  for(int i = 0; i < g.getAdjencyList().size(); ++i)
    for(int j = 0; j < g.neighbours(i).size(); ++i)
      f.push(i, g.neighbours(i)[j], false);

  vector<vector<int> >prevs (g.getSize());
  for(int i = 0; i < g.getSize();++i)
    prevs.push_back(vector<int>());

  for(int u = 0; u < g.getSize();++u)
    {
      vector<int> neighbs = g.neighbours(u);
      for(int i = 0; i < g.neighbours(u).size(); ++i)
	{
	  int v = neighbs[i];
	  prevs[v].push_back(u);
	}
    }
  //start algorithm
  vector<int> color(g.getSize());
  do
    {
      for(int i = 0; i < color.size(); ++i)
	color[i] = 0;
    }
  while(!fordFulkerson(f, color, g.getAdjencyList(), prevs, s, t));


  //Computing S & T
  for(int i = 0; i < g.getSize(); ++i)
    {
      if(color[i] == 2)
	S.push_back(i);
      if(color[i] == 0)
	T.push_back(i);
    }

  vector<int> result = intersect(X, T);
  vector<int>  tmp = intersect(Y, S);
  for(int i =  0; i < tmp.size(); ++i)
    result.push_back(tmp[i]);
  return result;


}

